package 经典排序算法;

import java.util.Scanner;

/**
 * @ClassName : 插入排序
 * @Author : 骆发茂
 * @Date: 2021/3/4 18:56
 * @Description :
 */
public class 插入排序_第一个数默认_取后面的数对比前面的数排序 {
    public static void main(String[] args) {
    System.out.println("请输入一个串数字，以空格作为分割，我将为你排序");
        System.out.println("=================================");
    Scanner scanner = new Scanner(System.in);
    String strings = scanner.nextLine();
    String[] newstrings = strings.split(" ");
    int[] array = new int[newstrings.length];
    for (int i = 0; i < newstrings.length; i++) {
        array[i] = Integer.parseInt(newstrings[i]);
    }
    System.out.println("==========原数组排序前为：===============");
    for (int j : array) {
        System.out.print(j + "  ");
    }
    System.out.println();
    System.out.println("==========数组排序后为：===============");
    insertionSort(array);
    for (int j : array) {
        System.out.print(j + "  ");
    }
    System.out.println();

}

    /**
     * 插入排序
     * @param array
     * @return
     */
    public static int[] insertionSort(int[] array) {
        if (array.length == 0)
            return array;
        int current;
        for (int i = 0; i < array.length - 1; i++) {/*默认第一个是已经排序好的，所以少一个*/
            current = array[i + 1];/*要变化，所以current是指下一个*/
            int preIndex = i;/*要变化，但i不能变，就新建跟i一样正常+1的，preIndex指当前这个*/
                                   /*array[i + 1]<array[i]*/
            while (preIndex >= 0 && current < array[preIndex]) {/*往前对比，但不要是负数，对比到第一个，而且如果  下一个 小于  当前这个*/
                /*array[i + 1] = array[i];*/
                array[preIndex + 1] = array[preIndex];/*把前面的放后面*/
                preIndex--;/*把数-1，再重复while循环，直到小的在前面，大的在后面*/
            }
            array[preIndex + 1] = current;/*退出了while循环，说明前面的没有比后面的大，就插在前方数的后面*/
        }
        return array;
    }
}
/*优化：「将一个数字插入一个有序的数组」这一步，可以不使用逐步交换，使用先赋值给「临时变量」，然后「适当的元素」后移，
空出一个位置，最后把「临时变量」赋值给这个空位的策略（就是上面那张图的意思）。
编码的时候如果不小心，可能会把数组的值修改，建议多调试；

特点：「插入排序」可以提前终止内层循环（体现在 nums[j - 1] > temp 不满足时），
在数组「几乎有序」的前提下，「插入排序」的时间复杂度可以达到 O(N)O(N)；

由于「插入排序」在「几乎有序」的数组上表现良好，特别地，在「短数组」上的表现也很好。
因为「短数组」的特点是：每个元素离它最终排定的位置都不会太远。为此，在小区间内执行排序任务的时候，可以转向使用「插入排序」。

复杂度分析：

时间复杂度：O(N^2)O(N
2
 )，这里 NN 是数组的长度；
空间复杂度：O(1)O(1)，使用到常数个临时变量。

public class Solution {

    // 插入排序：稳定排序，在接近有序的情况下，表现优异

    public int[] sortArray(int[] nums) {
        int len = nums.length;
        // 循环不变量：将 nums[i] 插入到区间 [0, i) 使之成为有序数组
        for (int i = 1; i < len; i++) {
            // 先暂存这个元素，然后之前元素逐个后移，留出空位
            int temp = nums[i];
            int j = i;
            // 注意边界 j > 0
            while (j > 0 && nums[j - 1] > temp) {
                nums[j] = nums[j - 1];
                j--;
            }
            nums[j] = temp;
        }
        return nums;
    }
}
*/